package by2019;

/*
 * 给定一个二叉树，找到该树中两个指定节点的最近公共祖先
 */

public class 二叉树的最近公共祖先 {

	public static void main(String[] args) {

	}
	//判断p，q是否分别在二叉树的两边，如果是的话，那么此二叉树的顶点就是要找的值
	//如果两个数在同一个子树的话，那么只需要迭代此子树
	//如果传入树的顶点是p或者q的话，那么这个顶点就是要找的树asdawdsadwasdwasdw
	public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		if(root==null || root==p ||root==q)
			return root ;
		TreeNode left = lowestCommonAncestor(root.left, p, q) ;
		TreeNode right = lowestCommonAncestor(root.right, p, q);
		//如果左子树为空，则返回右子树继续递归
		//如果右子树为空，则返回左子树继续递归
		//如果两个都不为空，则返回root
		return left==null?right : right==null?left : root ;
	}
	
	//二叉搜索树找祖先
	//可以通过判断p，q与树的顶点值的大小判断p，q属于哪边的子树
	 public TreeNode lowestCommonAncestorX(TreeNode root, TreeNode p, TreeNode q) {
			if(root==null || root==p ||root==q)
				return root ;
			if(p.val>root.val && q.val>root.val) {
				return lowestCommonAncestorX(root.right, p, q);
			} else if(p.val<root.val && q.val<root.val) {
				System.out.println("进入左子树判断，p.val="+p.val+" root.val="+root.val+"root.left="+root.left);
				return lowestCommonAncestorX(root.left, p, q) ;
			} 
			
			return root ;
			
	 }

}
